package Top_Interview_Questions_Review._001Tree;

import Top_Interview_Questions_Review._001Tree.Supple.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author: 吕庆龙
 * @Date: 2020/2/7 13:22
 * <p>
 * 功能描述:
 */
public class _0102 {

    public static void main(String[] args) {
        _0102 test = new _0102();

        TreeNode root = new TreeNode(3);
        TreeNode node1 = new TreeNode(9);
        TreeNode node2 = new TreeNode(20);
        TreeNode node3 = new TreeNode(15);
        TreeNode node4 = new TreeNode(7);
        TreeNode node5 = new TreeNode(6);
        TreeNode node6 = new TreeNode(11);

        root.left = node1;
        root.right = node2;
        node2.left = node3;
        node2.right = node4;
        node1.left = node5;
        node1.right = node6;

        List<List<Integer>> lists = test.levelOrder(root);
        System.out.println(lists);


    }

    /**
     *       3
     *     /   \
     *    9     20
     *   / \   /  \
     *  6  11 15   7
     *
     *  bfs的层序遍历
     */
    public List<List<Integer>> levelOrder1(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<List<Integer>>();
        if (root == null) return levels;

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);

        int level = 0;
        while ( !queue.isEmpty() ) {
            // 开始当前层级的遍历
            levels.add(new ArrayList<Integer>());

            // 当前层级的元素数量
            int level_length = queue.size();
            for(int i = 0; i < level_length; ++i) {
                TreeNode node = queue.remove();

                // 给当前层级填数据
                levels.get(level).add(node.val);

                //把当前层级的孩子节点加入到队列中,为下一层级遍历做准备
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
            // 去下一层级
            level++;
        }
        return levels;
    }


    /*--------------------------------------官方题解的递归--------------------------------------*/

    /**
     *       3
     *     /   \
     *    9     20
     *   / \   /  \
     *  6  11 15   7
     *
     *  dfs的层序遍历
     */
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null)
            return res;

        helper(root,0);
        return res;
    }

    public void helper(TreeNode cur, Integer level){
        if(res.size() == level)
            res.add(new ArrayList<Integer>());

        res.get(level).add(cur.val);

        if(cur.left != null)
            helper(cur.left,level+1);
        if(cur.right != null)
            helper(cur.right,level+1);
    }

    /*----------------------------------------------------------------------------------------*/




}
